#include<bits/stdc++.h>
using namespace std;
int tle;
int n;
int a[1001];
bool ans[1001];
int ma=0;
int dfs(int t){
    if(t==n){
        return 0;
    }
    t++;
    ans[t]=0;
    int k=0;
    for(int i=t-1;i>=1;i--){
        if(ans[i]==0){
            k=a[t];
            break;
        }
    }
    ma=dfs(t+1)+k;
    ans[t]=1;
    for(int i=t-1;i>=1;i--){
        if(ans[i]==1){
            k=a[t];
            break;
        }
    }
    ma=max(ma,dfs(t+1)+k);
    return ma;
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin>>tle;
    for(int i=1;i<=tle;i++){
        cin>>n;
        for(int j=1;j<=n;j++) cin>>a[j];
        cout<<dfs(0)<<" " ;
    }
    return 0;
}
